package com.chj.chuji.tijie14;

import java.util.ArrayList;

//https://blog.csdn.net/qq_41117236/article/details/87023967
//https://blog.csdn.net/wang_123_zy/article/details/86777193
public class Selected {

	public static class Node {
		int val;
		Node left;
		Node right;

		public Node(int val) {
			this.val = val;
		}
	}

//	public static class Node {
//		int left;
//		int right;
//
//		public Node(int l, int r) {
//			this.left = l;
//			this.right = r;
//		}
//	}

//	public static void get_arr(int x, HashMap<String, Integer> cntMap, int[] arr, Node[] p, int[] w) {
//		if (p[x].left > 0) {
//			get_arr(p[x].left, cntMap, arr, p, w);
//		}
//
//		if (p[x].right > 0) {
//			get_arr(p[x].right, cntMap, arr, p, w);
//		}
//
//		int cnt = cntMap.get("cnt");
//		arr[cnt++] = w[x];
//		cntMap.put("cnt", cnt);
//	}

	public static void posOrderRecur(Node head, ArrayList<Integer> arr) {
		if (head == null) {
			return;
		}
		posOrderRecur(head.left, arr);
		posOrderRecur(head.right, arr);
		arr.add(head.val);
	}

	public static int upper_bound(int l, int r, int x, int[] a) {
		while (l < r) {
			int mid = (l + r) / 2;
			if (a[mid] > x) {
				r = mid;
			} else {
				l = mid + 1;
			}
		}
		return l;
	}

	public static void main(String[] args) {
		int maxn = 6;
		int n = 5;
		int[] ar = new int[maxn];
		int[] dp = new int[maxn];

		Node n1 = new Node(1);
		Node n2 = new Node(5);
		Node n3 = new Node(4);
		Node n4 = new Node(2);
		Node n5 = new Node(3);

		n1.left = n3;
		n1.right = n2;
		n2.left = n4;
		n2.right = n5;
		ArrayList<Integer> arr02 = new ArrayList<Integer>();

		posOrderRecur(n1, arr02);
		int an = arr02.size();
		for (int i = 0; i < an; i++) {
			ar[an - i - 1] = arr02.get(i);
		}

		int len = 0;
		for (int i = 0; i < n; i++) {
			int pos = upper_bound(0, len, ar[i], dp);
			dp[pos] = ar[i];
			len = Math.max(len, pos + 1);
		}

		System.out.println(len);
	}
}

//#include <bits/stdc++.h>
//#define ll long long
//#define ull unsigned long long
//#define ms(a,b) memset(a,b,sizeof(a))
//#define INF 0x7f7f7f7f
//const int maxn=1e5+10;
//const int mod=1e9+7;
//using namespace std;
//int w[maxn];
//int arr[maxn];
//int ar[maxn];
//int dp[maxn];
//struct wzy
//{
//	int l,r;
//}p[maxn];
//int cnt;
//void get_arr(int x)
//{
//	if(p[x].l)
//		get_arr(p[x].l);
//	if(p[x].r)
//		get_arr(p[x].r);
//	arr[cnt++]=w[x];
//}
//int main(int argc, char const *argv[])
//{
//	ios::sync_with_stdio(false);
//	cin.tie(0);
//	ms(p,0);
//	int n,a,b;
//	cin>>n;
//	for(int i=1;i<=n;i++)
//		cin>>w[i];
//	for(int i=1;i<=n;i++)
//	{
//		cin>>a>>b;
//		p[i].l=a;
//		p[i].r=b;
//	}
//	get_arr(1);
//	for(int i=0;i<cnt;i++)
//		ar[cnt-i-1]=arr[i];
//	int len=0;
//	for(int i=0;i<n;i++)
//	{
//		int pos=upper_bound(dp,dp+len,ar[i])-dp;
//		dp[pos]=ar[i];
//		len=max(len,pos+1);
//	}
//	cout<<len<<endl;
//	return 0;
//}